#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
private:
    void dfs(string& store, vector<bool>& visit, vector<string>& ans, string& str) {
        if (str.size() == store.size()) {
            ans.emplace_back(store);
            return;
        }
        vector<bool> c_visit(128, false);
        for (int i = 0; i < visit.size(); i++) {
            if (!visit[i] && !c_visit[str[i]]) {
                c_visit[str[i]] = true;
                visit[i] = true;
                store.push_back(str[i]);
                dfs(store, visit, ans, str);
                store.pop_back();
                visit[i] = false;
            }
        }
    }
public:
    vector<string> permutation(string s) {
        if (s.empty()) {
            return {};
        }
        string store;
        vector<bool> visit(s.size());
        vector<string> ans;
        dfs(store, visit, ans, s);
        return ans;
    }
};

int main() {
    Solution solution;
    vector<string> output = solution.permutation("abc");
    for (string& it : output) {
        cout << it << endl;
    }
}